//给你一个整数数组 nums ，数组中的元素 互不相同 。返回该数组所有可能的子集（幂集）。 
//
// 解集 不能 包含重复的子集。你可以按 任意顺序 返回解集。 
//
// 
//
// 示例 1： 
//
// 
//输入：nums = [1,2,3]
//输出：[[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]]
// 
//
// 示例 2： 
//
// 
//输入：nums = [0]
//输出：[[],[0]]
// 
//
// 
//
// 提示： 
//
// 
// 1 <= nums.length <= 10 
// -10 <= nums[i] <= 10 
// nums 中的所有元素 互不相同 
// 
//
// Related Topics 位运算 数组 回溯 👍 2122 👎 0


package LeetCode.editor.cn;

import java.util.ArrayList;
import java.util.List;

/**
 * @author ldltd
 * @date 2023-08-26 02:23:09
 * @description 78.子集
 */
public class Subsets{
	 public static void main(String[] args) {
	 	 //测试代码
	 	 Solution solution = new Subsets().new Solution();
		int []nums={1,2,3};
		solution.subsets(nums).forEach(s-> System.out.println(s.toString()));
	 }
	 
//力扣代码
//leetcode submit region begin(Prohibit modification and deletion)
class Solution {
	/*时间 o(n*2^n)  空间on */
	public List<List<Integer>> subsets(int[] nums) {
		List<List<Integer>> res = new ArrayList<>();
		List<Integer> path = new ArrayList<>();
		dfs(nums, 0, path, res);
		return res;
	}

	private void dfs(int[] nums, int n, List<Integer> path, List<List<Integer>> res) {
		//长度为n的序列时终止
		if(n==nums.length){
			res.add(new ArrayList<>(path));
			return;
		}
			//考虑当前位置
			path.add(nums[n]);
			dfs(nums,n+1,path,res);
			//不考虑当前位置
			path.remove(path.size()-1);
			dfs(nums,n+1,path,res);
	}
	/*时间O(n×2^n)     空间On*/
	public List<List<Integer>> subsets2(int[] nums) {
		int n = nums.length;
		List<List<Integer>> res = new ArrayList<>();
		List<Integer>t=new ArrayList<>();
		/*数组中的所有数字，每一位，在或者不在，可以用01表示
		* 生成一个n长度的序列的数
		* 1<<n。即把1往左移位n，除了首位是1，其他位置都是0，
		* 则从0到这个数的每一个数，都可以表示一个状态
		* 然后用每个数去判断，当前位，是否在这次序列中
		* 比如长度为3，则n等于8，比如当i=5时，表示101，即有0和2号位
		* 比如判断2，是否在序列中，1<<2，等于0100
		* 100&101(5)=100不等于0，所以在序列中
		* 判断1,1<<1等于010&101=0，不在序列中
		* 即判断i的第j个位置是不是1*/
		for (int i = 0; i < (1<<n); i++) {
			t.clear();
			for (int j = 0; j < n; j++) {
				//判断这个数是不是在序列中
				if((i&(1<<j))!=0){
					t.add(nums[j]);
				}
			}
			res.add(new ArrayList<>(t));
		}
		return res;
	}
}
//leetcode submit region end(Prohibit modification and deletion)

}
